package algorithmPractice;

/*
 *@Description 链表反转
 *@Author llt
 *@Date 2021/5/17 20:29
 *@Version 1.0
 */
public class ReverseNode {

    public static void main(String[] args) {
        ReverseNode r = new ReverseNode();
        Node node = r.createNode(7);
        r.printNode(node);
//        Node reverOne = r.reverseNode(newNode);
//        r.printNode(reverOne);

//        Node reverOne2 = r.localReverseNode(node);
//        r.printNode(reverOne2);

        Node reverOne3 = r.headInsertReverse(node);
        r.printNode(reverOne3);

        //递归测试
        Node node2 = r.createNode(119);
        Node newNOde = r.reverseList(node2);
        r.printNode(newNOde);


        Node node3 = r.createNode(10);
        r.printNode(node3);
        Node newNOde3 = r.partReserseList(node3,2,6);
        r.printNode(newNOde3);


    }


    //就地反转法
    public Node reverseNode(Node head){
        if(head == null){
            return head;
        }
        Node newHead = new Node(-1);
        newHead.setNext(head);
        Node front = newHead.getNext();
        Node cur = front.getNext();
        while(cur != null){
            front.setNext(cur.getNext());
            cur.setNext(newHead.getNext());
            newHead.setNext(cur);
            cur = front.getNext();
        }
        return newHead.getNext();
    }

    //就地反转法
    public Node localReverseNode(Node head){
        if(head == null){
            return head;
        }
        Node newHead = new Node(-1);
        newHead.next = head;
        Node front = newHead.next;
        Node cur = front.next;
        while(cur != null){
            front.next = cur.next;
            cur.next = newHead.getNext();
            newHead.next = cur;
            cur = front.next;
        }
        return newHead.next;
    }


    //头插法
    public Node headInsertReverse(Node head){
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    //递归反转
    public Node reverseList(Node head) {
        if (head == null || head.next == null)
            return head;
        Node next = head.next;
        Node new_head = reverseList(next);
        next.next = head;
        head.next = null;
        return new_head;
    }


    /**
     * 部分反转单项列表
     */
    public  Node partReserseList(Node head, int from , int to) {
        int len = 0;
        Node node1 = head;
        Node tPre = null;
        Node tPos = null;
        // 找到第from-1个节点fPre和第to+1个节点tPos
        while (node1 != null) {
            len ++; //链表的索引
            tPre = len == from - 1 ? node1: tPre;
            tPos = len == to + 1 ? node1: tPos;
            node1 = node1.next;
        }
        if(from > to || from < 1 || to >len) {
            return null;
        }

        //node1为反转后的链表
        node1 = tPre == null ? head : tPre.next;
        Node node2 = node1.next;
        node1.next = tPos;
        Node next = null;
        while (node2 != tPos) {
            next = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = next;
        }
        if(tPre != null) {
            tPre.next = node1;
            return tPre;
        }

        return node1;
    }






    //创建链表
    public Node createNode(int length){
        Node head = null;
        Node cur = null;
        for(int i = 1 ; i< length; i++){
            Node next = new Node(i);
            if(i==1){
                head = next;
            }else{
                cur.setNext(next);
            }
            cur = next;
        }
        return head;
    }

    //打印链表
    public void printNode(Node head){
        StringBuilder sb = new StringBuilder("链表为：");
        sb.append(head.getValue()).append("-->");
        Node next = head.getNext();
        while(next != null){
            sb.append(next.getValue());
            next = next.getNext();
            if(next != null){
                sb.append("-->");
            }
        }
        System.out.println(sb);
    }

}
